The term "digital signal pattern" matching is here used in reference to the process of matching the digital encoding of an envelope pattern of an input signal time sequence against the envelope pattern of a reference signal time sequence. Such matching is involved in, for example, robotic control of a factory operation in which an object may be placed on a conveyor belt in an unpredictable location and orientation; and a robotic manipulator must be able to identify that location and orientation and manipulate the object appropriately. Another well known signal pattern matching application is in speech recognition systems in which a speech signal envelope representing a word or a syllable is compared against thousands of reference signal envelopes representing all of the possibilities of interest.
One way to perform such signal pattern matching is to correlate mathematically a perceived signal envelope pattern with the patterns of each of the reference possibilities and select the reference pattern with the maximum correlation with the input signal. Another example of such pattern matching is the dynamic time warp match of the continuous speech pattern recognizer in the C. S. Meyers et al. U.S. Pat. No. 4,400,788.
Signal pattern matching is to be distinguished from data, or value, pattern matching in which values of each of successive data segments of a sequence of input segments is compared, usually subtractively, against similar reference segments to identify all locations in the database of each input segment. Data pattern matching is often applied in information retrieval systems. One example of such data pattern matching occurs in rule-based systems, where values in "if" clauses of rules are matched against values of working memory, such as that in the paper "DADO: A Parallel Processor for Expert Systems" by S. J. Stolfo et al., "Proceedings of the 1984 International Conference on Parallel Processing," pages 74-82.
From the foregoing it can be seen that there are at least two distinctions between digital signal pattern matching and digital data pattern matching. One involves the nature of mathematical operations required: in signal pattern matching, the mathematical correlation requires many floating point multiplication/accumulation sequences to be performed, but in data pattern matching only fixed point additions and subtractions are required. A second distinction involves the size of patterns to be compared; that is, in signal pattern matching a typical pattern is thousands of digital words, but in data pattern matching a typical pattern is perhaps five to ten digital words. Each of the two distinctions involves a multiple-order-of-magnitude difference in numerical requirements making real time digital signal processing more difficult than data signal processing.
Highest processing speed is a significant goal for many designers; and, in the speech recognition arena, an objective of the U.S. Government has been to achieve real-time speech recognition in a 10,000-word speaker-independent system by the early 1990's. See "Strategic Computing New-Generation Computing Technology: A Strategic Plan for its Development and Application to Critical Problems in Defense," Defense Advanced Research Projects Agency, Oct. 28, 1983, page 35. In that plan it is estimated that computational requirements for such a system will be on the order of 20 billion instructions per second (BIPS). Those instructions essentially comprise multiplications and accumulations of multibit binary coded values, which in speech are preferably sixteen bits each for input and 32-bit floating point for subsequent computation.
In the "Sunday Star-Ledger" newspaper published in Newark, NJ, there appeared on Oct. 5, 1986, an article "Princeton `Brain trust` Top scientists plug into supercomputer" by K. MacPherson. That article mentioned a Cyber 250 single computer capable of about 800 million floating point operations per second (MFLOPS). The article also speaks of a planned ETA-10 computer system being manufactured and using up to eight processors, with liquid nitrogen cooling, costing about $10 million which is said to be capable of 10,000 million floating point operations per second (MFLOPS), i.e. a speed about half of the above-noted computational requirement goal-the units of instructions per second and operations per second being different words for the same thing.
Continuing in the multiprocessing direction, an L. Cosell et al. paper "Continuous Speech Recognition on a Butterfly.TM. Parallel Processor" at pages 717-720 of Proceedings of the 1986 Internatinal Conference on Parallel Processing speaks of, but does not illustrate, multiple processors arranged, with a switch and shared memory, for parallel operation. A maximum array of up to 256 microprocessor nodes is indicated. A specific example on a smaller scale included 15 tightly coupled microprocessor nodes and achieved recognition of a 3.5 second utterance in 11 seconds. The specific microprocessor chip used, at advertised numbers of cycles for multiplication and addition operations and specified minimum cycle time, is capable of about 200,000 such floating point operations per second (FLOPS); so the 256 processors in parallel operation should be capable of about 50 MFLOPS.
In the data pattern matching arena, one of the faster multiprocessing arrays is the binary tree. Such a tree and its capabilities are discussed at length in "The Tree Machine: A Highly Concurrent Computing Environment" by S. A. Browning in Technical Report (Ph.D. Thesis), Computer Science, California Institute of Technology, 1980. The processing element processor is considered at pages 132-134 and is described as including four main parts: a program store, a bank of data storage registers, an arithmetic logic unit (ALU), and some communication handlers. Current work is represented by, for example, the DADO multiprocessing system outlined in the aforementioned S. Stolfo et al. paper. Communication between nodes in Stolfo et al is by way of a three-link path including an input/output (I/O) link extending either up or down in the tree, a so-called handshake line extending both up and down in the tree, and a third link (upward from the node processor and downward from the node data memory). The handshake lines comprise an unbroken wire network extending throughout the tree, but the manner of preventing internode interference through that network is not shown. A DADO 1023-processing-element system was to have an unpipelined microprocessor at each element and was expected to be able to realize a top processing speed of about 570 million such instructions per second (MIPS).